/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-19
 * Time: 18:53
 */
public class test_3 {
    /**
     * 动态规划
     * @param n
     * @return
     */
    public static int dp1(int n){
        if (n == 1){
            return 1;
        }
        int[][]dp = new int[n + 1][n + 1];

        for (int i = 1;i <= n;i++){
            dp[i][0] = 1;
            dp[i][i] = 1;
        }

        for (int pre = n - 1; pre >= 1;pre--){
            for (int rest = pre + 1;rest <= n;rest++){
                int ways = 0;
                for (int i = pre; i <= rest;i++){
                    ways += dp[i][rest - i];
                }
                dp[pre][rest] = ways;
            }
        }
        return dp[1][n];
    }

    public static void main(String[] args) {
        System.out.println(dp1(5));
    }
}
